package com.leetcode.tree;

import com.study.common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-19 11:42
 * @version: 1.0
 * @description: 翻转二叉树
 **/
public class InvertTree {

    // 广度优先算法 (Breadth-First-Search)
    // 深度优先搜索 (Depth First Search)

    public TreeNode invertTree(TreeNode root) {
//        if (root == null) return null;
//        return dfs(root);
        return bfs(root);
    }

    // 广度优先一般需要借助队列实现
    private TreeNode bfs(TreeNode root) {
        if (root == null) return  null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();
            TreeNode temp = poll.left;
            poll.left = poll.right;
            poll.right = temp;
            if (poll.left != null){
                queue.offer(poll.left);
            }

            if (poll.right != null){
                queue.offer(poll.right);
            }
        }
        return root;
    }

    private TreeNode dfs(TreeNode root) {
        if (root == null) return null;
        TreeNode left = dfs(root.left);
        TreeNode right = dfs(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }




}
